Statement#

For a given array nums, determine if the array can be divided into two subarrays such that the sum of both the subarrays is equal.

For example, we have an array [1,2,3][1, 2, 3]:

  • The total length of this array can be denoted as nn that is 33.

  • An array can only be divided into two equal subarrays if the total sum of the array is even. In this case, the total sum of array elements is 1+2+3=61 + 2 + 3 = 6, so two equal sum subarrays can be obtained here, as [1,2][1, 2] and [3][3], both having an equal sum of 33.

  • In this case, TRUE will be returned as the array can be divided into two equal sum subarrays.

  • In case, the sum of array elements is odd or the array can not be divided into two equal sum subarrays, FALSE will be returned.

Constraints:

  • 11 \leqnums.length 200\leq 200

  • 11 \leq nums[i] 100\leq 100

Examples#

No.

nums

Result

1

[1, 2, 3]

TRUE

2

[4, 2, 7]

FALSE

3

[2, 1, 5, 3, 1]

TRUE

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Equal sum subarrays

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

We can solve this problem with the following two steps:

  1. First, we calculate the sum of the array. If the sum of the array is odd, there can’t be two subarrays with an equal sum. Therefore, we return FALSE.

  2. If the sum is even, we calculate Target Sum == Array Sum/2/2 and find a subarray of the array with a sum equal to Target Sum. The subarray can be found by either including the current element or not including it. To include the current element, we need to subtract it from the Target Sum.

The first step can be calculated easily, and the second can be solved using recursion. In the recursive approach, we calculate the result repeatedly by decreasing the problem set and evaluating the solution at every stage. For example, consider an array [1, 2, 3, 2, 6, 2], that can be partitioned into [1, 2, 3, 2] and [6, 2], with the sum equal to 8.

Let’s implement the algorithm as discussed above:

Equal Sum Subarrays using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of this approach is O(2n)O(2^n). In the worst case, for each element in the array, this solution tests two possibilities, whether to include or exclude it.

Space complexity#

Since we can’t have more than nn recursive calls on the call stack at any time, the space complexity of this approach is O(n)O(n).

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array.

As the recursive approach shows, the sum 6 + 2 = 8 is computed twice, which takes extra time. We can avoid the repeated work done in the naive approach by storing the result calculated at each step.

We can use a dictionary named Memo that will store two things; the index of the element and the target sum. Using memoization and recursion to go further for any element in the array, we can:

  • Choose that element, in which case, the Target Sum will be updated as Target Sum == Target Sum - Nums [i].

  • If we ignore the ithi^{th} element and move forward, Target Sum will remain the same.

  • If Target Sum ==0==0, then return TRUE.

  • If Target Sum <0< 0, then return FALSE.

Let’s implement the algorithm as discussed above:

Equal Sum Subarrays using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity for this approach is O(n×s)O(n \times s), where nn is the number of array elements and ss is the target sum.

Space complexity#

Since we are using a dictionary to store two things, the array index and the target sum, the space complexity of this approach is O(n×s)O(n \times s).

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. The problem is divided into subproblems, which are dependent on each other. We create a 2-D table of dimensions (n+1)×(s+1)(n + 1) \times (s + 1), where nn is the size of the array and ss is the Target Sum calculated as Target Sum = Array Sum/2/2, to store the result of subproblems. If we encounter the same sub-problem later, we can return the stored result from the table with a O(1)O(1) lookup instead of recalculating that subproblem.

We will use the previously computed subproblem’s results in further calculations to fill the table indices by:

  1. Place FALSE (0)(0) in the first row of the table and TRUE (1)(1) in the first column of the table.

  2. Let’s assume that the dp[i][j]dp[i][j] means whether the Target Sum jj can be achieved from the first ii elements. If we can pick a series of numbers from 00 to ii whose sum is jj, then dp[i][j]dp[i][j] is TRUE. Otherwise, it is FALSE.

    The above step can be computed by using the following:

    dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j]
  3. Return the value of the last index of the table, which denotes whether the array can be partitioned.

    • If we get 11 (TRUE), the array can be partitioned.

    • If we get 00 (FALSE), the array can not be partitioned.

The value for dp[1][1]dp[1][1] can be calculated with the help of dp[0][0]dp[0][0] and dp[1][0]dp[1][0], which are computed earlier. We don’t need to compute them again, which is the advantage of dynamic programming.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6

1 of 12

Created with Fabric.js 3.6.6

2 of 12

Created with Fabric.js 3.6.6

3 of 12

Created with Fabric.js 3.6.6

4 of 12

Created with Fabric.js 3.6.6

5 of 12

Created with Fabric.js 3.6.6

6 of 12

Created with Fabric.js 3.6.6

7 of 12

Created with Fabric.js 3.6.6

8 of 12

Created with Fabric.js 3.6.6

9 of 12

Created with Fabric.js 3.6.6

10 of 12

Created with Fabric.js 3.6.6

11 of 12

Created with Fabric.js 3.6.6

12 of 12

Let’s implement the algorithm as discussed above:

Equal Sum Subarrays using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

The time complexity of the above solution is O(n×s)O(n \times s), where nn is the size of the input array, and ss is the target sum.

Space complexity#

The space complexity of the above solution is O(n×s)O(n \times s), as the table has a dimension (n+1)×(s+1)(n + 1) \times (s + 1), where nn is the size of the array, and ss is the target sum.

Minimum Number of Refueling Stops

Count Square Submatrices